//: [Previous](@previous)

//排序算法

import Foundation
let str = "Hello, playground"

var array = [7,0,4,5,0,3,6]
var array2 = [4,5,6,3,2,1]
var array3 = [1,3,2,4,5,6,7,8]


class Solution {
    func merge(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
        var idx1 = 0
        var idx2 = 0
        var insertIdx = 0
        var newArr = [Int]()
        while idx1 < m && idx2 < n {
            let a = nums1[idx1]
            let b = nums2[idx2]
            if a < b {
                newArr.append(a)
                idx1 += 1
            }else{
                newArr.append(b)
                idx2 += 1
            }
            insertIdx += 1
        }
        //如果数组有剩余
        if idx1 < m {
            newArr += nums1[idx1...m-1]
        }
        if idx2 < n {
            newArr += nums2[idx2...n-1]
        }
        print(newArr)
        nums1 = newArr
    }
    
    func merge2(_ nums1: inout [Int], _ m: Int, _ nums2: [Int], _ n: Int) {
        nums1.removeSubrange(m...nums1.count - 1)
        nums1 += nums2[0..<n]
        nums1.sort()
        print(nums1)
    }
}
var nums1 = [1,2,3,0,0,0]
var nums2 = [2,5,6]
//Solution().merge2(&nums1, 3, nums2, 3)




/* 选择排序
 */
func selectionSort(array: inout Array<Int>) -> Array<Int> {
    print(array)
    //遍历
    for i in 0..<array.count {
        //遍历,随后的所有的元素
        for j in i+1..<array.count {
            //当前元素
            let current = array[i]
            //下一个元素
            let next = array[j]
            //如果当前元素大于下一个,交换2个元素的位置
            if current > next {
                array[i] = next
                array[j] = current
            }
        }
        print(array)
    }
    return array
}
//selectionSort(array: &array2)


// MARK: - 冒泡排序
/*  1.进行n次遍历, 比较两个相邻元素的大小, 然后交换位置
 *  2.通过标记是否有交换, 来确认是否提前退出
 *  时间复杂度n^2
 */
func bubbleSort(array: inout Array<Int>) -> Array<Int> {
    for _ in 0..<array.count {
        //数据交换标志位
        var flag = false
        for j in 0..<array.count - 1 {
            if array[j] > array[j+1]  {
                array.swapAt(j, j+1)
                //有数据交换
                flag = true
            }
        }
        //如果没有数据交换
        if flag == false {
            break
        }
        print(array)
    }
    return array
}
bubbleSort(array: &array2)


// MARK: - 插入排序
//插入排序,通过交换 [7,0,4,5,0,3,6]
func insertionSort2(_ arr: inout Array<Int>) {
    //从第2个开始取
    for i in 1..<arr.count {
        let current = arr[i]
        //比较当前值和之前所有
        for j in 0..<i {
            //已排序数组中current
            let temp = arr[j]
            if current < temp {
                arr.remove(at: i)
                arr.insert(current, at: j)
                print(arr)
                break
            }
        }
    }
}
insertionSort2(&array)


//插入排序
func insertionSort(_ arr: Array<Int>) {
    //新建数组
    var newArr = [arr.first!]
    //遍历旧数组后面的所有元素
    for i in 1..<arr.count {
        //当前元素
        let current = arr[i]
        var min: Int? = nil
        //遍历新数组
        for j in 0..<newArr.count {
            if current < newArr[j] {
                newArr.insert(current, at: j)
                min = current
                break
            }
        }
        if min == nil {
            newArr.append(current)
        }
    }
    print(newArr)
}


// MARK: - 选择排序
//选择排序
func chooseSort(_ arr: inout Array<Int>) -> Array<Int> {
    for i in 0..<arr.count {
        //记录当前最小值
        var minIdx = i
        //找到最小值
        for j in i+1..<arr.count {
            if arr[minIdx] > arr[j] {
                minIdx = j
            }
        }
//        arr.swapAt(i, minIdx)
        //取出最小值
        let temp = arr[minIdx]
        //将最小值位替换为索引值
        arr[minIdx] = arr[i]
        //将索引位替换为最小值
        arr[i] = temp

    }
    return arr
}

func chooseSort2(_ arr: inout Array<Int>) -> Array<Int> {
    for i in 0..<arr.count {
        var minIdx = i
        for j in i+1..<arr.count {
            if arr[minIdx] > arr[j] {
                minIdx = j
            }
        }
        arr.swapAt(minIdx, i)
    }
    return arr
}

var nums = [3,4,2,6,1,7,9]
chooseSort2(&nums)







//print(maopaoSort(array: &array))
//print(chooseSort(&array))
//insertionSort(&array)






